#include "kmp.h"

/**
 * 对模式串进行匹配分析
 * 
 * 网上有的版本也叫next数组
 * 
 * @param pattern   模式串
 * 
 * @return  分析后的结果
 */
static inline std::vector<int> BuildMatch(std::string_view pattern) {
  auto p_len = pattern.length();
  std::vector<int> match(p_len, -1);  // match里面存放的匹配失败的转移下标
                                      // 所以这里的默认值必须是-1
  auto k = -1;  // 当前匹配的位置 默认不匹配 初始化为 -1

  // 从第二位开始遍历模式串，只遍历一遍，不回退
  for (auto i = 1; i < p_len; ++i) {
    while (-1 != k && pattern[k + 1] != pattern[i]) {
      // 已经处于匹配过程中时发生不匹配的情况，k需要回退
      k = match[k];
    }
    if (pattern[k + 1] == pattern[i]) {
      // 进入匹配模式 k变为当前已经匹配的串位置
      ++k;
    }
    match[i] = k;  // 记录当前模式串中可以回退的位置
  }

  return std::move(match);
}

std::string::size_type KMPMatch(std::string_view target,
                                std::string_view pattern) {
  auto t_len = target.length();
  auto p_len = pattern.length();

  do {
    if (p_len > t_len) {
      break;
    }
    auto match = BuildMatch(pattern);

    auto p_i = -1;

    for (auto t_i = 0; t_i < t_len; ++t_i) {
      while (-1 != p_i && pattern[p_i + 1] != target[t_i]) {
        p_i = match[p_i];
      }

      if (pattern[p_i + 1] == target[t_i]) {
        ++p_i;
      }
      if (p_i == p_len - 1) {
        return t_i - p_len + 1;
      }
    }
  } while (0);

  return std::string::npos;
}
